package 所有的题类.F.树;

import 所有的题类.ZA.链表.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class 二叉树的锯齿形层序遍历 {

    public static void main(String[] args) {
        二叉树的锯齿形层序遍历 a=new 二叉树的锯齿形层序遍历();
        int[]array={1,2,3,4,5,6,7};
        TreeNode treeNode = arrayToTreeNode(array, 0, array.length - 1);
        List<List<Integer>> lists = a.zigzagLevelOrder(treeNode);
        System.out.println(lists.size());
    }
    //层序遍历
    public List<List<Integer>> cengxubianli(TreeNode root){
        List<List<Integer>> allList=new ArrayList();
        Queue<TreeNode> queue=new LinkedList();
        queue.add(root);
        boolean flag=false;
        while(queue.size()>0){
            int size=queue.size();
            List<Integer> level = new ArrayList();
            List<Integer> revserLevel = new ArrayList();
            flag=!flag;
            for(int i=0;i<size;i++){
                TreeNode node= queue.poll();
                if(flag){
                    level.add(node.val);
                }else{
                    revserLevel.add(node.val);
                }
                //将新的节点推入到队列里面
                if(node.left!=null){
                    queue.add(root.left);
                }
                if(node.right!=null){
                    queue.add(root.right);
                }
            }
            if(flag){
                allList.add(level);
            }else{
                allList.add(reverList(revserLevel));
            }
        }
        return allList;
    }

    public List<Integer> reverList(List<Integer> list){
        List<Integer> newList=new ArrayList();
        for(int j=list.size()-1;j>=0;j--){
            newList.add(list.get(j));
        }
        return newList;
    }

    public static TreeNode arrayToTreeNode(int[]array,int left,int right){
        TreeNode root=null;
        if(right>=left){
            int mid=(left+right+1)/2;
            root = new TreeNode(array[mid]);
            TreeNode leftNode = arrayToTreeNode(array, left, mid-1);
            TreeNode rightNode = arrayToTreeNode(array, mid + 1, right);
            root.left=leftNode;
            root.right=rightNode;
        }else{
            root=null;
        }
        return root;
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        return cengxubianli(root);
    }

}
